class MinStack {
    Deque<Integer> st;
    Deque<Integer> minSt;  // 维护一个单调栈
    /*
        对于单调栈，当push元素的时候，如果栈为空，或者新增的元素比栈顶的元素更小或等于，那么就压入栈
        当pop元素时候，如果栈顶元素和minSt的栈顶元素相同，就把minSt元素弹出

     */
    public MinStack() {
        st = new LinkedList<>();
        minSt = new LinkedList<>();
    }
    public void push(int val) {
        st.push(val);
        // 为什么要小于等于呢？考虑插入2,1,1 的情况
        if( minSt.isEmpty() || val<=minSt.peek()){
            minSt.push(val);
        }
    }
    public void pop() {
        int val = st.pop();
        if( val == minSt.peek() ){
            minSt.pop();
        }
    }
    public int top() {
        return st.peek();
    }
    public int getMin() {
        return minSt.peek();
    }
}


class MinStack {
    Deque<Integer> st;
    Deque<Integer> minSt;  // 维护一个单调栈
    public MinStack() {
        st = new LinkedList<>();
        minSt = new LinkedList<>();
        minSt.push(Integer.MAX_VALUE);
    }

    public void push(int val) {
        st.push(val);
        minSt.push(Math.min(val,minSt.peek()));
    }

    public void pop() {
        st.pop();
        minSt.pop();
    }

    public int top() {
        return st.peek();
    }

    public int getMin() {
        return minSt.peek();
    }
}

